#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    long long maxSpending(vector<vector<int>>& values) {
        using LL = long long;
        struct cmp
        {
            bool operator()(pair<int, int> a, pair<int, int> b) { return a.first > b.first; }
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> heap;
        int m = values.size();
        for (int i = 0; i < m; i++)
        {
            heap.push({ values[i].back(), i });
            values[i].pop_back();
        }
        LL res = 0, day = 1;
        while (heap.size())
        {
            auto pair = heap.top(); heap.pop();
            res += pair.first * day;
            day++;
            int index = pair.second;
            if (values[index].size())
            {
                heap.push({ values[index].back(), index });
                values[index].pop_back();
            }
        }
        return res;
    }
};